package com.example.leetcode;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * 单调栈
 * 移除k个数字保持最小
 * 1 <= k <= num.length <= 105
 * num 仅由若干位数字（0 - 9）组成
 * 除了 0 本身之外，num 不含任何前导零
 *
 * 思路2 不出栈就入栈 去掉后缀多余
 */
public class Demo0402 {

    public static void main(String[] args) {
        System.out.println(removeKdigits1("10001",4));
    }

    public static String removeKdigits(String num, int k) {
        int len = num.length();
        Deque<Character> stack=new ArrayDeque<>();
        int index=0;
        int count=len -k;
        /**
         * 边界条件剩余长度字得大于0
         */
        if (count<=0){
            return "0";
        }
        while (index<len){

            //下标小于长度 && （栈空或大于栈顶） && 栈长小于剩余长度 入栈 并且下标自增
            while (index<len && (stack.isEmpty() || stack.peekLast()<=num.charAt(index)) && (stack.size()<count)){
                stack.addLast(num.charAt(index++));
            }

            //下标到字符长度跳出
            if (index==len){
                break;
            }

            //栈不空  && 小于栈顶  && 栈长加剩余数字大于剩余长度 则出栈
            while (!stack.isEmpty() && stack.peekLast()>num.charAt(index)
            && stack.size()+len-index-1>=count){
                stack.removeLast();
            }

            //下标一定小于长度；栈顶一定小于等于当前；只需判断栈长小于剩余长度即可入栈
            if (stack.size() < count) {
                stack.addLast(num.charAt(index));
            }
            //无论入栈否都需要自增
            index++;
        }

        //判断是否多个0
        while (!stack.isEmpty() && stack.peekFirst()=='0' && stack.size()!=1){
            stack.removeFirst();
        }
        StringBuilder sb=new StringBuilder();
        index=0;
        while (!stack.isEmpty() && index<count){
            sb.append(stack.removeFirst());
            index++;
        }
        return sb.toString();
    }

    public static String removeKdigits1(String num, int k){
        int len = num.length();
        int count=len-k;
        if (count<=0){
            return "0";
        }
        Deque<Character> stack=new ArrayDeque<>();
        stack.addLast('0');
        for (int i = 0; i < len; i++) {

            char curChar = num.charAt(i);
            //1.考虑出栈
            while (curChar<stack.peekLast() && len-i+stack.size()>count+1){
                stack.removeLast();
            }

            //2.必定入栈
            stack.addLast(curChar);
        }

        //3.截长度
        while (stack.size()>count+1){
            stack.removeLast();
        }

        //4.去头0和哨兵
        while (stack.size()>1 && stack.peekFirst()=='0'){
            stack.removeFirst();
        }

        StringBuilder sb=new StringBuilder(count);
        while (!stack.isEmpty()){
            sb.append(stack.removeFirst());
        }
        return sb.toString();
    }
}
